Steven_Meng's Blog

传送门
题意：求最大团，团是一个点的集合，其中任意两点都有边相连。
最大团属于$NPC$问题None Player Characters
虽然数据范围小，$n \le 50$，但是直接暴搜肯定超时。
考虑随机化，每次打乱点的总集合$S$
从$S$中取出点$v$，若$v$与$Ans$中的所有点都有边相连，则将$v$加入$Ans$，否则跳过$v$

实践证明随机化个$1000$次就能$AC$

正确性显（bu）然（hui）

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define MAXN 55
using namespace std;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') {
        x=(x*10)+(ch-'0');
        ch=getchar();
    }
    return x*f;
}
int G[MAXN][MAXN];
void AddEdge(int u,int v){
    G[u][v]=true;
    G[v][u]=true;
}
int a[MAXN];
int stk[MAXN],top;
int main(){
    int n=read(),u,v;
    int maxn=0;
    while (scanf("%d%d",&u,&v)!=EOF&&u!=0&&v!=0){
		AddEdge(u,v);
		maxn=max(maxn,u),maxn=max(maxn,v);
	}
    for (register int i=1;i<=n;++i){
    	a[i]=i;
	}
    int ans=-0x7fffffff;
    srand(time(NULL));
    for (register int k=0;k<10000;++k){
        random_shuffle(a+1,a+1+n);
        top=0;
        stk[++top]=a[1];
        for (register int i=2;i<=n;++i){//找出v
        	bool flag=true;
        	for (register int j=1;j<=top;++j){//判断是否有边相连
        		if (!G[stk[j]][a[i]]){
        			flag=false;
        			break;
				}
			}
			if (flag==true){
				stk[++top]=a[i];//加入集合Ans
			}
		}
		ans=max(ans,top);
    }
    printf("%d\n",ans);
}